The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of links (communication paths such as telephone or optical lines) and nodes (usually routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
De-activation of a network component, i.e. a link or a node, either by component failure or by planned downtime needs to be managed in order to avoid the risk of packet loss. In known systems, such de-activations cause routing transitions to take place, during which, distributed routing algorithms may open up an alternative route. However such transitions can be slow, of the order of seconds before convergence and in the interim data can be lost. Although packet loss is commonly dealt with by higher level protocols that re-send packets, the inherent delays can adversely affect time critical functions such as voice and pseudo-wire traffic.
Various solutions have been proposed for providing backup routes.
For example in Multi-Protocol Label Switching (MPLS) fast re-route, pre-configured backup paths are provided for destinations, as described in the document entitled “MPLS Traffic Engineering Fast Reroute—Link Protection” available at the time of this writing in the file ‘frr.pdf’ in directory “univercd/cc/td/doc/product/software/ios120/120newft/120limit/120st/120st16” of the domain “cisco.com” on the World Wide Web. However MPLS backup paths rely on source routing.
Various other proposals based on link state routing rely on “downstream paths” according to which a node determines whether an alternative path to a destination node is available which will not simply loop a packet back to it (i.e. the packets will travel “downstream”). Examples of such proposals are the Internet Draft of Kini, Yang, dated May 2002 entitled “Traffic Restoration in Links State Protocols using Neighbor's Shortest Path” available at the time of this writing in the file ‘draft-kini-traf-restore-nsp-00.txt’ in directory “internet-drafts” of the domain “ietf.org” on the World Wide Web. A further example is Srinivas Vutukury, “Multi-Path Routing Mechanisms for Traffic Engineering and Quality of Service in the Internet”PhD Thesis, computer Science, University of California, Santa Cruz, March 2001. However such solutions will not work if no downstream path is available.
Zhang Yang and Jon Crowcroft in the paper “Shortest Path First with Emergency Exits” ACM SIGCOMM Computer Communication Review Volume 209, Issue 4 (September 1990) propose a solution according to which, for a given destination node an alternative path (AP) is created to the shortest path (SP) for a specified node to the destination using a downstream path (i.e. a path which will get a packet closer to its destination than the current node) identified by calculating whether any of the specified node's neighbor nodes can reach the destination without looping back to the specified node. If, for any destination in the network, an AP is not available, then the specified node sends a message to each of its neighbors to assess whether any of their neighbors can provide a downstream path to the destination. If not then the message is propagated out once again until an “exit” to the destination node is identified, providing a “reverse alternative path” (RAP). The specified node maintains a table, for every destination, of the SP and AP and, where an AP is not available an RAP.
Various problems arise with this approach. First of all because it relies on a signaling protocol in order to establish whether an RAP is available, the process is time-and bandwidth-consuming. Furthermore in order to forward a packet to an exit in an RAP the source has to force it upstream, potentially over a number of hops which requires source routing. As a result an additional protocol is overlaid on the link state protocol and the processing burden of the specified node is also increased.